package com.code.test.ali;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.md
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * <p>
 * candidates 中的数字可以无限制重复被选取。
 * <p>
 * 说明：
 * <p>
 * 所有数字（包括 target）都是正整数。
 * 解集不能包含重复的组合。
 * 示例 1：
 * <p>
 * 输入：candidates = [2,3,6,7], target = 7,
 * 所求解集为： [ [7], [2,2,3] ]
 * 示例 2：
 * <p>
 * 输入：candidates = [2,3,5], target = 8,
 * 所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]
 */
public class TCode39 {

    public static void main(String[] args) {
        int[] nums = {2, 3, 6, 7};
        List<List<Integer>> ret = combine(nums, 7);
        System.out.println(ret.size());
        System.out.println(ret);
    }


    /**
     * 元素可以重复使用
     */

    static List<List<Integer>> ret = new ArrayList<>();
    static List<Integer> temp = new ArrayList<>();

    public static List<List<Integer>> combine(int[] nums, int target) {
        bt(nums, target, 0);
        return ret;
    }

    public static void bt(int[] nums, int target, int startIndex) {
        int sum = temp.stream()
                .mapToInt(Integer::intValue)
                .sum();
        if (sum == target) {
            ret.add(new ArrayList<>(temp));
            return;
        }

        /**
         * 不能包含重复的组合
         * 但是可以包含重复元素
         * 因为在同一个组合里面找，所以有index
         * 此时index+1？取决于元素是否能重复，可以重复不加，不可以重复就+1
         * 原因是：
         * [2,3,,6,7]
         * 2->跟[2,3,6,7]这条链路比，比完之后，可以有重复，简单理解就是2&2，可以跟自身，这条链路完了，就把2剔除掉了
         * 剩下[3,6,7]，此时思路跟上面一样
         * 以此类推
         *
         * 如果不能重复，则index+1
         * [2,3,6,7]
         * 2 跟[3,6,7]比，带着2，3跟[6,7]比，一直往下，元素要减少，这条链路走完，就把2踢掉了
         * 剩下[3,6,7], 3跟[6,7]比，带着3，6跟[7]比
         *
         */
        for (int i = startIndex; i < nums.length; i++) {
            int cur = nums[i];
            if (sum + cur > target) {
                continue;
            }
            temp.add(cur);
            bt(nums, target, i);
            temp.remove(temp.size() - 1);
        }
    }
}
